package Question;

/**
 * @author leiyuee
 * @ClassName Question.Josephu 约瑟夫问题：小孩出圈 →环形单向链表
 * @date 2021/11/9 9:55
 */
public class Josephu {


    class Boy {
        private int no;
        private Boy next;

        public Boy(int no) {
            this.no = no;
        }

        public int getNo() {
            return no;
        }

        public void setNo(int no) {
            this.no = no;
        }

        public Boy getNext() {
            return next;
        }

        public void setNext(Boy next) {
            this.next = next;
        }
    }

    class CircleSingleLinkedList {
        private Boy first = null;

        public void addBoy(int nums) {
            if (nums < 1) {
                System.out.println("nums的值不正确");
                return;
            }
            Boy cruBoy = null;
            for (int i = 1; i <= nums; i++) {
                Boy boy = new Boy(i);
                if (i == 1) {
                    first = boy;
                    first.setNext(first);
                    cruBoy = first;
                } else {
                    cruBoy.setNext(boy);
                    boy.setNext(first);
                    cruBoy = boy;
                }


            }


        }

        public void showBoy(){
            if (first ==null){
                System.out.println("没有小孩");
                return;
            }
            Boy cruBoy = null;
            while (true){
                System.out.println("小孩的编号为："+cruBoy.getNo());
                if (cruBoy.getNext() ==first){
                    break;
                }
                cruBoy = cruBoy.getNext();
            }
        }

        //根据用户的输入，计算出小孩出圈的顺序
        public void  countBoy(int startNo,int countNum,int nums){
            if (first ==null||startNo<1||startNo>nums) {
                System.out.println("参数有误，请重新输入");
                return;
            }
            Boy helper = first;
            //让helper 指向环形链表的组以后节点
            while (true){
                if (helper.getNext() == first){//是最后一个了
                    break;
                }
                helper = helper.getNext();
            }
            //报数前，让first 和 helper 移动startNo-1此
            for (int j =0;j<startNo-1;j++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //报数时
            while (true){
                if (helper ==null){ //只有一个
                    break;
                }
                for (int j =0;j<countNum-1;j++){
                    first = first.getNext();
                    helper = helper.getNext();
                }

                System.out.printf("小孩%d出圈\n",first.getNo());
                first.getNext();
                helper.setNext(first);
            }
            System.out.printf("最后留在圈里的小孩编号为%d\n",first.getNo());

        }

    }

}
